/**
 * Oregon licence plates consist of three letters followed by a three digit 
 * number (each digit can be from [0..9]). While driving to work Seth plays 
 * the following game: Whenever the numbers of two licence plates seen on his
 * trip add to 1000 that's a win.
 *
 * E.g. MIC-012 and HAN-988 is a win and RYU-500 and SET-500 too. (as long as
 * he sees them in the same trip, not necessarily consecutively).
 *
 * Find the expected number of plates he needs to see for a win.
 * Give your answer rounded to 8 decimal places behind the decimal point.
 *
 * Note: We assume that each licence plate seen is equally likely to have any
 * three digit number on it.
 */

#include <iostream>
//#include <stdio.h>
#include "euler.h"

BEGIN_PROBLEM(371, solve_problem_371)
	PROBLEM_TITLE("Licence plates")
	PROBLEM_ANSWER("40.66368097")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("n")
	PROBLEM_SPACE_COMPLEXITY("1")
	PROBLEM_KEYWORDS("probability")
END_PROBLEM()

/* Let N = 2*M be the total number of plates with different digits. In this
 * problem, N = 1000 and M = 500. These plates can be grouped into 500 pairs
 * according to their sum, except with 000 and 500 grouped in a special pair,
 * like below:
 *
 *   1-pair  (M-1) pairs
 *   0       1    2    ...  499
 *   500     999  998  ...  501
 *
 * Let f(m, 0) be the expected number of plates to see for a win, given that
 * he has already seen m pair-free, non-zero, non-500 numbers. Similarly,
 * let f(m, 1) be the expected number of plates to see for a win, given that
 * he has already seen m pair-free, non-zero, non-500 numbers, plus already
 * seen 500. We need to distinguish these two cases because 500 must be paired
 * with itself, while the rest numbers are paired with a different number.
 *
 * We then find the following recursive relation for f(m, 0) and f(m, 1):
 *
 *   f(m,0) = 1 + P(X = 0)  * f(m,0) 
 *              + P(X = M)  * f(m,1) 
 *              + P(X seen) * f(m,0)
 *              + P(X not seen and pair-free)*f(m+1,0)
 *
 *   f(m,1) = 1 + P(X = 0)  * f(m,1) 
 *              + P(X = M)  * 0
 *              + P(X seen) * f(m,1)
 *              + P(X not seen and pair-free)*f(m+1,0)
 *
 * In both equations we denote X as the number on the next plate. Plugging in
 *
 *   P(X = 0)  = 1/N, 
 *   P(X = M)  = 1/N, 
 *   P(X seen) = m/N, 
 *   P(X not seen and pair-free) = 2*(M-1-m)/N,
 *
 * we can solve the recursive relation as
 *
 *              N + f(m,1) + 2*(M-1-m)*f(m+1,0)
 *    f(m,0) = ---------------------------------
 *                          N-m-1
 *
 *              N + 2*(M-1-m)*f(m+1)
 *    f(m,1) = ----------------------
 *                     N-m-1
 *
 * This is a tail recursion that can be computed in linear time of N and
 * with constant space. The answer to the problem is f(0, 0).
 */

static void solve_problem_371()
{
	const int N = 1000, M = N / 2;

    /* Compute boundary value when m = M - 1. */
    int m = M - 1;
    double f1 = 2.0;
    double f0 = 2.0 + 2.0 / M;

    /* Recursively compute f(m,1) and f(m,0) backward. */
    while (--m >= 0)
    {
        f1 = (N + 2.0*(M-1-m)*f1) / (N-m-1);
        f0 = (N + f1 + 2.0*(M-1-m)*f0) / (N-m-1);
    }

    /* Print answer. */
#if 0
    printf("%.8lf\n", f0);
#else
    std::cout.precision(8);
    std::cout << std::fixed << f0 << std::endl;
#endif
}
